package dp;

public class lengthOfLIS {
    public int lengthOfLIS(int[] nums) {
        int[] dp =new int[nums.length];
        for(int i=0;i<dp.length;i++){
            dp[i]=1;
        }
        int max=1;
        for(int i=1;i<dp.length;i++){
            int step=0;
            for(int j=0;j<i;j++){
                if (nums[i]>nums[j]) {
                    step=Math.max(step, dp[j]);
                }
            }
            dp[i]+=step;
            max=Math.max(max, dp[i]);
        }
        return max;
    }
    public static void main(String[] args) {
        lengthOfLIS obj = new lengthOfLIS();
        // int[]nums = new int[]{10,9,2,5,3,7,101,18};
        int[]nums = new int[]{0,1,0,3,2,3};
        // int[]nums = new int[]{7,7,7,7};
        System.out.println(obj.lengthOfLIS(nums));
    }
}
